package acm;

/**
 * 递归的优化
 * 
 * @author Administrator
 * 
 */
public class Digui {

	public static void main(String[] args) {

		System.out.println(fibonacci(6));
		System.out.println("jump" + jump(100));
		double d1, d2;
		d1 = 1.3569;
		d2 = 1.3659;
		if (d1 == d2) {
			System.out.println(true);
		}
	}

	// 斐波那契的优化，由于斐波那契数列调用递归的时候会分别计算F(n-1),F(n-2);
	// F(n-1)又由F（n-2）和F(n-3)求，可见有很多重复的计算
	// 遇到重复的计算或者操作的想法就是换一下顺序，即从0,1开始算起
	public static long fibonacci(int n) {
		if (n < 0) {
			System.err.println("输入有误");
			return 0;
		}
		if (n < 2) {
			return n == 0 ? 0 : 1;
		}
		long fibOne = 0;
		long fibTwo = 1;
		long fibN = 0;
		for (int i = 2; i <= n; i++) {
			fibN = fibOne + fibTwo;
			fibOne = fibTwo;
			fibTwo = fibN;
		}
		return fibN;
	}

	// 跳台阶
	public static long jump(int n) {
		if (n <= 0) {
			System.err.println("输入有误");
			return 0;
		}
		if (n <= 2) {
			return n;
		}
		long fibOne = 1;
		long fibTwo = 2;
		long fibN = 0;
		for (int i = 3; i <= n; i++) {
			fibN = fibOne + fibTwo;
			fibOne = fibTwo;
			fibTwo = fibN;
		}
		return fibN;
	}
}
